<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="zh-cn">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
<title>深入浅出说编译原理(一) - 刘水镜 - 博客园</title>
<link type="text/css" rel="stylesheet" href="/bundles/blog-common.css?v=CFo7qU8PX574D_uabaLip0eHAfPkOQKz7wVlSUf2A9Q1"/>
<link id="MainCss" type="text/css" rel="stylesheet" href="/skins/SimpleBlue/bundle-SimpleBlue.css?v=g1Ly_5CnmgosFgcSP2WTmRocMrlS6IO9yhcnMXW9dOA1"/>
<link title="RSS" type="application/rss+xml" rel="alternate" href="http://www.cnblogs.com/liushuijinger/rss"/>
<link title="RSD" type="application/rsd+xml" rel="EditURI" href="http://www.cnblogs.com/liushuijinger/rsd.xml"/>
<link type="application/wlwmanifest+xml" rel="wlwmanifest" href="http://www.cnblogs.com/liushuijinger/wlwmanifest.xml"/>
<script src="http://common.cnblogs.com/script/jquery.js" type="text/javascript"></script>  
<script type="text/javascript">var currentBlogApp = 'liushuijinger', cb_enable_mathjax=false;</script>
<script src="/bundles/blog-common.js?v=dVqr0ue7y29mRAG2afMkFcSk38ChENfNlXrmAf_YHQE1" type="text/javascript"></script>
</head>
<body>
<a name="top"></a>

<div id="home">
<div id="header">
	<div id="blogTitle">
		
<!--done-->
<div class="title"><a id="Header1_HeaderTitle" class="headermaintitle" href="http://www.cnblogs.com/liushuijinger/">不受天磨非好汉,不遭人妒是庸才——刘水镜</a></div>
<div class="subtitle"></div>



		
	</div><!--end: blogTitle 博客的标题和副标题 -->
	<div id="navigator">
		
<ul id="navList">
<li id="nav_sitehome"><a id="MyLinks1_HomeLink" class="menu" href="http://www.cnblogs.com/">博客园</a></li>
<li id="nav_myhome"><a id="MyLinks1_MyHomeLink" class="menu" href="http://www.cnblogs.com/liushuijinger/">首页</a></li>
<li id="nav_q"><a class="menu" href="http://q.cnblogs.com/">博问</a></li>
<li id="nav_ing"><a class="menu" href="http://home.cnblogs.com/ing/">闪存</a></li>
<li id="nav_newpost"><a id="MyLinks1_NewPostLink" class="menu" rel="nofollow" href="http://i.cnblogs.com/EditPosts.aspx?opt=1">新随笔</a></li>
<li id="nav_contact"><a id="MyLinks1_ContactLink" class="menu" rel="nofollow" href="http://space.cnblogs.com/msg/send/%e5%88%98%e6%b0%b4%e9%95%9c">联系</a></li>
<li id="nav_rss"><a id="MyLinks1_Syndication" class="menu" href="http://www.cnblogs.com/liushuijinger/rss">订阅</a>
<!--<a id="MyLinks1_XMLLink" class="aHeaderXML" href="http://www.cnblogs.com/liushuijinger/rss"><img src="http://www.cnblogs.com/images/xml.gif" alt="订阅" /></a>--></li>
<li id="nav_admin"><a id="MyLinks1_Admin" class="menu" rel="nofollow" href="http://i.cnblogs.com/">管理</a></li>
</ul>

		<div class="blogStats">
			
			
<!--done-->
随笔-169&nbsp;
文章-0&nbsp;
评论-755&nbsp;

			
		</div><!--end: blogStats -->
	</div><!--end: navigator 博客导航栏 -->
</div><!--end: header 头部 -->
<div id="main">
	<div id="mainContent">
	<div class="forFlow">
		

<!--done-->
<div id="topics">
	<div class = "post">
		<h1 class = "postTitle">
			<a id="cb_post_title_url" class="postTitle2" href="http://www.cnblogs.com/liushuijinger/archive/2012/05/09/2490972.html">深入浅出说编译原理(一)</a>
		</h1>
		<div class="clear"></div>
		<div class="postBody">
			<div id="cnblogs_post_body"><p><span style="font-family: 'Microsoft YaHei'; font-size: 16px; line-height: 24px;">个人认为编译原理对于一个程序员来说很重要，可能你认为编程的时候用的都是C++、C#、Java等高级语言，至于编译原理懂与不懂并无大碍。其实不然，所谓万变不离其宗，所有高级语言的诞生都是基于最根本的编译原理的。搞懂了编译原理，对于一个程序员的能力提升有着很大的帮助。因为它会让你对编程有更加深刻的理解，有助于你写出质量更高的代码。好废话不多说，切入正题！</span></p>
<p><span style="line-height: 24px;"><span style="font-family: 'Microsoft YaHei'; font-size: 16px;">本文主要说一下编译原理里的文法、正规式、有穷自动机和语法推导树。</span></span></p>
<p> <span style="line-height: 24px;"><span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><br />
	</span></span>
</p>
<p>
	<span style="line-height: 24px;"><span style="font-family: 'Microsoft YaHei';"><span style="font-size: 18px;"><strong>文法</strong></span></span></span>
</p>
<p>
	<span style="line-height: 24px;"><span style="font-family: 'Microsoft YaHei';"><span style="font-size: 18px;"><strong><br />
	</strong></span></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;">文法就是计算机语言的一个严格的规范，有点类似人类语言的语法。就像形容词修饰名词，副词修饰形容词跟动词类似，只不过计算机的文法的标准和规范更加的严格而已。</span></span>
</p>
<p>
	<span style="line-height: 24px;"><span style="font-size: 16px; font-family: 'Microsoft YaHei';">文法的表达式：</span><span style="color: #333333; line-height: 26px; text-align: left;"><span style="font-family: 'Microsoft YaHei'; font-size: 16px;">G=(Vn,Vt,P,S) &nbsp;Vn是非终结符的集合，Vt是终结符的集合，P是推导式的一个集合，S是开始符。</span></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;">文法中有三种符号和四种文法类型：</span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;">三种符号为：开始符&mdash;&mdash;S；非终结符&mdash;&mdash;A、B、C、AB等；终结符&mdash;&mdash;a、b、c等。其实说白了开始符就是Start的缩写，非终结符就是大写字母或大写字母的组合（开始符S也是非终结符），终结符就是小写字母或小写字母的组合。</span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;">文法共分为四种，即0型文法&mdash;&mdash;短语文法；1型文法&mdash;&mdash;上下文有关文法；2型文法&mdash;&mdash;上下文无关文法；3型文法&mdash;&mdash;正规文法。</span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><span style="font-family: 'Microsoft YaHei'; font-size: 16px; line-height: 24px;">四个文法类的定义是逐渐增加限制的，即每一种正规文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是短语文法。称0型文法产生的语言为0型语言。上下文有关文法、上下文无关文法和正规文法产生的语言分别称为</span><span style="font-family: 'Microsoft YaHei'; font-size: 16px; line-height: 24px;">上下文有关语言</span><span style="font-family: 'Microsoft YaHei'; font-size: 16px; line-height: 24px;">、上下文无关语言和正规语言。</span><br />
	</span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><span style="font-family: 'Microsoft YaHei'; font-size: 16px; line-height: 24px;"><strong><span style="color: #ff6666;">注意：除0型文法以外，每一种文法都必须符合上一种文法。</span></strong></span></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><span style="font-family: 'Microsoft YaHei'; font-size: 16px; line-height: 24px;"><strong><span style="color: #ff6666;"><br />
	</span></strong></span></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><strong>0型文法：</strong></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;">书中的定义：<span style="line-height: 24px;">设G=(VN，VT，P，S)，如果它的每个产生式&alpha;&rarr;&beta;是这样一种结构：&alpha;&isin;( VN&cup;VT )*且至少含有一个非终结符，而&beta;&isin;( VN&cup;VT )*，则G是一个0型文法。</span></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><span style="line-height: 24px;">通俗的解释：即产生式左边至少有一个大写字母，右边随意。</span></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><span style="line-height: 24px;"><br />
	</span></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><span style="line-height: 24px;"><strong>1型文法：</strong></span></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;">书中的定义：<span style="line-height: 24px;">设G=(VN，VT，P，S)，若P中的每一个产生式&alpha;&rarr;&beta;均满足|&beta;|&ge;|&alpha;| ，仅仅S&rarr;&epsilon;除外，则文法G是1型文法。</span></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><span style="line-height: 24px;">通俗的解释：即产生式左边的字母个数必须大于等于右边的字母个数。</span></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><span style="line-height: 24px;"><br />
	</span></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><span style="line-height: 24px;"><strong>2型文法：</strong></span></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><span style="line-height: 24px;">书中的定义：<span style="line-height: 24px;">设G=(VN，VT，P，S)，若P中的每一个产生式&alpha;&rarr;&beta;满足：&alpha;是一非终结符，&beta;&isin;( VN&cup;VT )*则此文法称为2型文法。</span></span></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><span style="line-height: 24px;"><span style="line-height: 24px;">通俗的解释：即产生式左边必须完全都是大写字母。</span></span></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><span style="line-height: 24px;"><span style="line-height: 24px;"><br />
	</span></span></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><span style="line-height: 24px;"><span style="line-height: 24px;"><strong>3型文法：</strong></span></span></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><span style="line-height: 24px;"><span style="line-height: 24px;">书中的定义：<span style="line-height: 24px;">设G=(VN，VT，P，S)，若P中的每一个产生式的形式都是A&rarr;aB或A&rarr;a，其中A和B都是非终结符，a是终结符，则G是3型文法。</span></span></span></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><span style="line-height: 24px;"><span style="line-height: 24px;"><span style="line-height: 24px;">通俗的解释：即所有产生式右边要么没有大写字母，如果有必须全部在小写字母右边或者全部在小写字母左边也就是要保持线性一致。</span></span></span></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><br />
	</span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><br />
	</span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei';"><span style="line-height: 24px;"><span style="font-size: 18px;"><strong>正规式</strong></span></span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><br />
	</span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;">正规式是由正规文法转换而来，它们之间的转换规则共有三条：</span></span>
</p>
<p>&nbsp;</p>
<p style="color: #333333; line-height: 26px; text-align: left;">
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;">规则1：正规文法（A&mdash;&gt;xB,B-&gt;y ），正规式（A=xy）。这点很简单，用小学的数学知识就可以解决！如：A=xB，B=y，那么A=xy。</span>
</p>
<p style="color: #333333; line-height: 26px; text-align: left;">
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;">规则2：正规文法（<span style="color: #333333; font-family: 'Microsoft YaHei'; line-height: 26px; text-align: left; font-size: 16px;">A&mdash;&gt;xA|y</span>），正规式（<span style="color: #333333; font-family: 'Microsoft YaHei'; line-height: 26px; text-align: left; font-size: 16px;">A=x*y</span>）。这是一个递归，它其实是&mdash;&mdash;<span style="color: #333333; font-family: 'Microsoft YaHei'; line-height: 26px; text-align: left; font-size: 16px;">正规文法（</span><span style="color: #333333; font-family: 'Microsoft YaHei'; line-height: 26px; font-size: 16px;">A&mdash;&gt;xA，<span style="color: #333333; font-family: 'Microsoft YaHei'; line-height: 26px; text-align: left; font-size: 16px;">A&mdash;&gt;y</span></span><span style="color: #333333; font-family: 'Microsoft YaHei'; line-height: 26px; text-align: left; font-size: 16px;">），因为<span style="color: #333333; font-family: 'Microsoft YaHei'; line-height: 26px; text-align: left; font-size: 16px;">A&mdash;&gt;xA，而右边的A又可以有<span style="color: #333333; font-family: 'Microsoft YaHei'; line-height: 26px; text-align: left; font-size: 16px;">A&mdash;&gt;xA，所以就可以无限循环下去，</span></span></span>最终还是要有结尾的，要不就没法表示了，所以有A=x*y，表明<span style="color: #333333; font-family: 'Microsoft YaHei'; line-height: 26px; text-align: left; font-size: 16px;">有无穷个</span>x并以y结尾。</span>
</p>
<p style="color: #333333; line-height: 26px; text-align: left;">
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;">规则3：A&mdash;&gt;x,A-&gt;y。那么A=x|y。这个就很简单了，不过多解释了。</span>
</p>
<p style="color: #333333; line-height: 26px; text-align: left;">
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><br />
	</span>
</p>
<p style="color: #333333; line-height: 26px; text-align: left;">
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;">其实上面说的那些话完全可以用下面一个表来代替，简单而又明了，哈哈！</span>
</p>
<p>&nbsp;</p>
<p style="text-align: center;">
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><img src="http://my.csdn.net/uploads/201204/25/1335287289_8672.jpg" alt="" /><br />
	</span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><br />
	</span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;">有穷自动机跟语法推导树留到下一篇博客再为大家讲解吧！敬请期待！</span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><br />
	</span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><br />
	</span></span>
</p>
<p>
	<span style="font-family: 'Microsoft YaHei'; font-size: 16px;"><span style="line-height: 24px;"><br />
	</span></span>
</p></div><div id="MySignature"></div>
<div class="clear"></div>
<div id="blog_post_info_block">
<div id="BlogPostCategory"></div>
<div id="EntryTag"></div>
<div id="blog_post_info">
</div>
<div class="clear"></div>
<div id="post_next_prev"></div>
</div>


		</div>
		<div class = "postDesc">posted @ <span id="post-date">2012-05-09 07:52</span> <a href='http://www.cnblogs.com/liushuijinger/'>刘水镜</a> 阅读(<span id="post_view_count">...</span>) 评论(<span id="post_comment_count">...</span>)  <a href ="http://i.cnblogs.com/EditPosts.aspx?postid=2490972" rel="nofollow">编辑</a> <a href="#" onclick="AddToWz(2490972);return false;">收藏</a></div>
	</div>
	<script type="text/javascript">var allowComments=true,isLogined=false,cb_blogId=101948,cb_entryId=2490972,cb_blogApp=currentBlogApp,cb_blogUserGuid='905fc6f4-2e10-e111-b422-842b2b196315',cb_entryCreatedDate='2012/5/9 7:52:00';loadViewCount(cb_entryId);</script>
	
</div><!--end: topics 文章、评论容器-->
<a name="!comments"></a><div id="blog-comments-placeholder"></div><script type="text/javascript">var commentManager = new blogCommentManager();commentManager.renderComments(0);</script>
<div id="comment_form" class="commentform">
<a name="commentform"></a>
<div id="divCommentShow"></div>
<div id="comment_nav"><span id="span_refresh_tips"></span><a href="javascript:void(0);" id="lnk_RefreshComments" onclick="return RefreshCommentList();">刷新评论</a><a href="#" onclick="return RefreshPage();">刷新页面</a><a href="#top">返回顶部</a></div>
<div id="comment_form_container"></div>
<div class="ad_text_commentbox" id="ad_text_under_commentbox"></div>
<div id="site_nav_under"><a href="http://www.cnblogs.com/" target="_blank" title="开发者的网上家园">博客园首页</a><a href="http://q.cnblogs.com/" target="_blank" title="程序员问答社区">博问</a><a href="http://news.cnblogs.com/" target="_blank" title="IT新闻">新闻</a><a href="http://home.cnblogs.com/ing/" target="_blank">闪存</a><a href="http://job.cnblogs.com/" target="_blank">程序员招聘</a><a href="http://kb.cnblogs.com/" target="_blank">知识库</a></div>
<div id="opt_under_post"></div>
<script type="text/javascript">
    var enableGoogleAd = canShowAdsense(); var googletag = googletag || {}; googletag.cmd = googletag.cmd || [];
    fixPostBodyFormat();
</script>
<div id="ad_under_post_holder">
<script type='text/javascript'>
    var googletag = googletag || {};
    googletag.cmd = googletag.cmd || [];
    (function () {
        if (enableGoogleAd) {
            var gads = document.createElement('script');
            gads.async = true;
            gads.type = 'text/javascript';
            var useSSL = 'https:' == document.location.protocol;
            gads.src = (useSSL ? 'https:' : 'http:') + '//www.googletagservices.com/tag/js/gpt.js';
            var node = document.getElementsByTagName('script')[0];
            node.parentNode.insertBefore(gads, node);
        }
    })();
</script>
<script type='text/javascript'>
    try {
        if (enableGoogleAd) {
            googletag.cmd.push(function () {
                googletag.defineSlot('/1090369/cnblogs_blogpost_C1_sitehome', [300, 250], 'div-gpt-ad-1346480159711-0').addService(googletag.pubads());
                googletag.defineSlot('/1090369/cnblogs_blogpost_C2', [468, 60], 'div-gpt-ad-1410860226396-0').addService(googletag.pubads());
                googletag.pubads().enableSingleRequest();
                googletag.enableServices();
            });
        };
    } catch (e) { }
</script>
<div id="google_ad_c1" class="c_ad_block">
    <div id='div-gpt-ad-1346480159711-0' style='width:300px; height:250px;'>
    <script type='text/javascript'>
        try {
            if (enableGoogleAd) {
                googletag.cmd.push(function () { googletag.display('div-gpt-ad-1346480159711-0'); });            
            } else {
                $('#div-gpt-ad-1346480159711-0').hide();
            }
    } catch (e) { }
    </script>
    </div>
</div>
</div>
<div id="under_post_news"></div>
<div id="google_ad_c2" class="c_ad_block">
<div id='div-gpt-ad-1410860226396-0' style='width:468px; height:60px;'>
<script type='text/javascript'>
try {
    if (enableGoogleAd) {
        googletag.cmd.push(function () { googletag.display('div-gpt-ad-1410860226396-0'); });
    } else {
        $('#div-gpt-ad-1346480159711-0').hide();
    }
} catch (e) { }
</script>
</div>
</div>
<div id="under_post_kb"></div>
<div id="HistoryToday" class="c_ad_block"></div>
<script type="text/javascript">
$(function () {
    loadNewsAndKb();
    loadBlogSignature();
    LoadPostInfoBlock(cb_blogId, cb_entryId, cb_blogApp, cb_blogUserGuid);
    GetPrevNextPost(cb_entryId, cb_blogId, cb_entryCreatedDate);
    loadOptUnderPost();
    GetHistoryToday(cb_blogId, cb_blogApp, cb_entryCreatedDate);
    setTimeout(function () { incrementViewCount(cb_entryId); }, 200);
});
</script>
</div>

	</div><!--end: forFlow -->
	</div><!--end: mainContent 主体内容容器-->

	<div id="sideBar">
		<div id="sideBarMain">
			
<!--done-->
<div class="newsItem">
<h3 class="catListTitle">公告</h3>
	<div id="blog-news"></div><script type="text/javascript">loadBlogNews();</script>
</div>

			<div id="calendar"><div id="blog-calendar" style="display:none"></div><script type="text/javascript">loadBlogDefaultCalendar();</script></div>
			
			<div id="leftcontentcontainer">
				<div id="blog-sidecolumn"></div><script type="text/javascript">loadBlogSideColumn();</script>
			</div>
			
		</div><!--end: sideBarMain -->
	</div><!--end: sideBar 侧边栏容器 -->
	<div class="clear"></div>
	</div><!--end: main -->
	<div class="clear"></div>
	<div id="footer">
		
<!--done-->
Copyright &copy;2015 刘水镜
	</div><!--end: footer -->
</div><!--end: home 自定义的最大容器 -->
</body>
</html>
